package com.kevin.Code.Backtrack;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname NQueensii
 * @Description Leetcode 52 N皇后 回溯算法 困难  和题Leetcode 51 思路一样
 * @Date 2021/9/23 11:32
 * @Version 1.0
 */
public class NQueensii {

    int res = 0;

    public int totalNQueens(int n) {

        if (n == 1) {
            return 1;
        }

        HashSet<Integer> columns = new HashSet<>();
        //用于存储左对角线
        HashSet<Integer> leftDiagonal = new HashSet<>();
        //用于存储右对角线
        HashSet<Integer> rightDiagonal = new HashSet<>();


        backtrack(columns, leftDiagonal, rightDiagonal, n, 0);

        return res;
    }

    /**
     * @param columns
     * @param leftDiagonal
     * @param rightDiagonal
     * @param n
     * @param row
     */
    public void backtrack(HashSet<Integer> columns, HashSet<Integer> leftDiagonal, HashSet<Integer> rightDiagonal, int n, int row) {

        if (n == row) {
            res += 1;
        } else {
            for (int i = 0; i < n; i++) {

                if (columns.contains(i)) {
                    continue;
                }

                //如果包含左斜线 跳过
                //左斜线上得数行列相减值相同
                int left = row - i;
                if (leftDiagonal.contains(left)) {
                    continue;
                }
                //右斜线行列坐标相加和相同
                int right = row + i;
                if (rightDiagonal.contains(right)) {
                    continue;
                }

                columns.add(i);
                leftDiagonal.add(left);
                rightDiagonal.add(right);
                //进入下一层
                backtrack(columns, leftDiagonal, rightDiagonal, n, row + 1);

                columns.remove(i);
                leftDiagonal.remove(left);
                rightDiagonal.remove(right);

            }

        }

    }
}
